BOJ_17298_오큰수

Stack을 사용해서 오른쪽에 있는 나보다 큰 수를 구하는 문제
나보다 큰 수가 많으면 가장 왼쪽에 있는 걸로 선택한다

그냥 n을 0부터 돌면서 오른쪽 숫자랑 비교하면 n이 100만이기 때문에 1초 안에 들어올 수는 없다. 그래서 뒤에서부터 탐색하는 것이 효율적이다. 여기까지 생각하니까 Stack 문제의 전형적인 유형인 스카이라인 로직이 떠올랐다. BOJ_1863_스카이라인 쉬운거 참고~!

건물 높이 -> 숫자로만 바뀐 형태다

# N이 100만이기 때문에 선형 시간, log n, nlongn까지만 가능하다(1초)  
#  
# 원소를 탐색하기 위해 o(n)은 디폴트로 소요된다  
#  
# 오른쪽에 있으면서 현재값보다 큰 가장 '왼쪽'에 있는 수  
#  
# -> 그냥 하나씩 함색하게 되면 o(n^2)가 나와서 실패한다  
#  
# 스택을 사용해서 뒤에서부터 탐색하면 O(n)에 끝낼 수 있따  
  
N = int(input())  
num_list = list(map(int, input().split()))  
stack = []  
res = []  
  
for i in range(N - 1, -1, -1):  
    now = num_list[i]  
    while True:  
        if not stack:  
            res.append(-1)  
            break  
  
        if stack[-1] > now:  
            res.append(stack[-1])  
            break  
  
        stack.pop()  
  
    stack.append(now)  
  
res = [str(x) for x in res][::-1]  
print(' '.join(res))